package binarytree;

import java.util.LinkedList;
import java.util.Queue;

class  BTNode{
    public char val;// 数据域
    public BTNode left;// 左孩子 / 左子树
    public BTNode right;// 右孩子 / 右子树
    public BTNode(char val){// 构造方法
        this.val = val;
    }
}

public class MyBinaryTree {
    public BTNode root; // 二叉树的根结点
    public BTNode creationTree(){
        BTNode A = new BTNode('A');
        BTNode B = new BTNode('B');
        BTNode C = new BTNode('C');
        BTNode D = new BTNode('D');
        BTNode E = new BTNode('E');
        BTNode F = new BTNode('F');
        BTNode G = new BTNode('G');
        BTNode H = new BTNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.left = H;
        return A;// 返回 根结点 A
    }
    // 获取 二叉树节点个数 - 遍历思维
    int count;
    public int size(BTNode root){
        if(root == null){
            return  0;
        }
        count++;
        size(root.left);
        size(root.right);
        return count;
    }
    // 获取 二叉树节点个数 - 子问题思维
    public int size2(BTNode root){
        if(root == null){
            return  0;
        }
        return size2(root.left) + size2(root.right)+1;
    }

    // 获取叶子结点个数 - 遍历思维
    int count2;
    public int getLeafNode(BTNode root){
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            count2++;
        }
        getLeafNode(root.left);
        getLeafNode(root.right);
        return count2;
    }

    // 获取叶子结点个数 - 子问题思维
    public int getLeafNode2(BTNode root){
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        return getLeafNode2(root.left) + getLeafNode2(root.right);
    }

    // 获取第K层节点的个数
    public int getLevelNode(BTNode root,int k){
        if(root == null){
            return 0;
        }
        if(k==1){
            return 1;
        }
        return getLevelNode(root.left,k-1) + getLevelNode(root.right,k-1);
    }

//    获取二叉树的高度
    public int getHeight(BTNode root){
        if(root == null){
            return 0;
        }
        return  Math.max(getHeight(root.left),getHeight(root.right)) + 1;
    }

    // 检测值为value的元素是否存在
    public BTNode find(BTNode root,char value){
        if(root == null){
            return null;
        }
        if(root.val == value){// 判断根结点是不是 指定的数据
            return  root;
        }
        BTNode node1 = find(root.left,value);// 查找 左子树 是有存在 指定value值的节点【找到了，返回其引用，否，则返回null】
        BTNode node2 = find(root.right,value);// 查找 右子树 是有存在 指定value值的节点【找到了，返回其引用，否，则返回null】
        return node1 == null ? node2:node1;// 如果 node1 为 null，说明左子树没有指定value值的节点，返回 node2【右子树的查找的结果】
        // 如果 node2 也没有，也没有关系，反正都是返回null，node2找到了更好。返回其节点的引用
    }

    // 判断 二叉树是否是是完全二叉树
    public boolean isCompleteTree(BTNode root){
        if(root == null){
            return true;
        }
        Queue<BTNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            BTNode tmp = queue.poll();
            if(tmp != null){
                queue.offer(tmp.left);
                queue.offer(tmp.right);
            }else{
                break;
            }
        }
        while(!queue.isEmpty()){
            BTNode tmp = queue.poll();
            if(tmp != null){
                return false;
            }
        }
      return true;
    }

    // 层次遍历
    public void levelTraversal(BTNode root){
        if(root == null){
            return;
        }
        Queue<BTNode> q = new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty()){
            BTNode tmp = q.poll();
            System.out.print(tmp.val +" ");
            if(tmp.left != null){
                q.offer(tmp.left);
            }
            if(tmp.right != null){
                q.offer(tmp.right);
            }
        }
    }

    // 前序遍历
    public void preorderTraversal(BTNode root){
        if(root == null){
            return;
        }
        System.out.print(root.val + " ");
        preorderTraversal(root.left);
        preorderTraversal(root.right);

    }
    // 中序序遍历
    public void inorderTraversal(BTNode root){
        if(root == null){
            return;
        }
        inorderTraversal(root.left);
        System.out.print(root.val + " ");
        inorderTraversal(root.right);

    }
    // 后序遍历
    public void postorderTraversal(BTNode root){
        if(root == null){
            return;
        }
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        System.out.print(root.val + " ");
    }
}
